import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board string字符串一维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean exist (String[] board, String word) {
        // write code here
         if(board == null || word==null){
            return false ;
         }

       char[][] array = new char[board.length][board[0].length()];
       for(int i = 0 ; i < board.length ; i++){
        for(int j = 0 ; j < board[0].length() ; j++){
             array[i][j] = board[i].charAt(j);
        }
       }
       boolean flg = false ;
       for(int i =0 ; i < array.length ; i++){
            for(int j = 0 ; j < array[0].length ; j++){
               if(array[i][j] == word.charAt(0)){
                 flg = check(array , i , j , word , 0);
               }
               if(flg){
                return true ;
               }
            } 
       }
         return false ;
    }
     private boolean check(char[][] array , int x , int y , String word , int index ){
           if(x<0 || y < 0 || x >= array.length || y >= array[0].length || index >= word.length()){
            return false ;
           }
           if(array[x][y] == word.charAt(index) && index+1 == word.length()){
            return true ;
           }
           if(array[x][y] != word.charAt(index)) {
               return false;
           }
           return  check(array , x , y+1 , word , index+1) ||
                  check(array , x , y-1 , word , index+1) ||
                  check(array , x+1 , y , word , index+1);
     }



}